Searchable data structures containing related data elements are well-known in the art. One simple example of such a structure is the data stack. In a stack, the data elements occupy successive address locations in computer memory, and are generally arranged in a predetermined order (i.e., alphabetical, numerical, etc.) in order to facilitate searching. Of course, one obvious disadvantage of such a structure is that the addition or removal of a data element would require massive reallocation of data element storage in order to preserve the order required for an effective search.
A linked list data structure eliminates this requirement for reordering upon modification of the structure. In a singly linked list, a pointer to the next element in the list is stored along with the data element itself. If a new item is inserted, the only restructuring required is the modification of the link pointers for the two elements between which the new element is inserted. For removal of an element in the list, only one link pointer need be changed to point to its new successor. Linked lists require more memory than stack data structures, since each element of the list must have an associated pointer. Searching also takes longer, since both link pointer values and data element values must be examined during execution of the search procedure.
Singly linked data structures, as described above, are searchable in one direction only (the direction in which the links are constructed). A doubly linked list, which has pointers associated with both the predecessor and successor elements of each data element, is capable of being searched in either direction, but at the cost of greatly increased memory overhead to accommodate storage of more pointer elements.
Even a doubly linked list, however, is not a suitable data structure when each data record contains multiple related elements. It is often necessary to build a data structure having the capability to be searched for one of two related items in order to find the other. For example, large personal information data bases containing data elements such as Social Security Number (SSN) and person's name lose substantial utility if a search cannot be conducted that yields a person's name in response to an SSN entry, or returns the SSN if the name is entered.
Data bases constructed for use in communication systems are often subjected to the constraint of real time search capability in addition to limited memory availability. Systems that depend for efficient operation upon the capability to rapidly search data bases for related identification (ID) information cannot operate effectively in an environment that inherently requires large amounts of memory and limits search speed.
Accordingly, a need arises for a data structure that supports rapid searches for related data elements without imposing excessive memory requirements.